package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * @Classname GenerateTrees_0095
 * @Author happytaohaha
 * @Date 2020/3/23
 * @Description 95. 不同的二叉搜索树 II
 * 卡特兰数学习： https://blog.csdn.net/NumberOneStudent/article/details/105048193
 *  G(n): 是构建一颗卡特兰数所用时间    时间和空间复杂度：nG(n)
 *
 */
public class GenerateTrees_0095 {


    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return generate_trees(1, n);
    }


    public LinkedList<TreeNode> generate_trees(int start, int end) {
        LinkedList<TreeNode> all_trees = new LinkedList<TreeNode>();
        if (start > end) {
            all_trees.add(null);
            return all_trees;
        }
        // 根节点
        for (int i = start; i <= end; i++) {
            // 所有不同的左子树的 left（start， i-1 ）
            LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);

            // 所有不同的右子树的 right（start， i-1 ）
            LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);

            // left * right
            for (TreeNode l : left_trees) {
                for (TreeNode r : right_trees) {
                    TreeNode current_tree = new TreeNode(i);
                    current_tree.left = l;
                    current_tree.right = r;
                    all_trees.add(current_tree);
                }
            }
        }
        return all_trees;
    }

}
